package Sort;

import java.util.Stack;

/**
 * 时间复杂度:
 *       最好的情况下：O(N*logN)
 *       最坏情况下：O(N^2) 逆序/有序
 * 空间复杂度:
 *       最好的情况下：O(logN)
 *       最坏情况下：O(N) 逆序/有序
 * 稳定性:
 *      不稳定
 */
public class QuickSort {
    public void Sort(int[] array)
    {
//        quick(array, 0, array.length - 1);
        quickNor(array);
    }

    private void quickNor(int[] array) {
        int start = 0;
        int end = array.length - 1;
        Stack<Integer> stack = new Stack<>();

        int pivot = partition(array, start, end);
        if(pivot > start + 1)
        {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if(pivot + 1 < end)
        {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while (!stack.isEmpty())
        {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array, start, end);
            if(pivot > start + 1)
            {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if(pivot + 1 < end)
            {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    private void quick(int[] array, int start, int end) {
        //优化1: 在趋于有序时使用插入排序
        if(end - start + 1 <= 15)
        {
            insertSort(array, start, end);
            return;
        }

        //优化2: 使基数尽量在中间
        int index = middleNum(array, start, end);
//        int pivot = partitionHoare(array, start, end);//Hoare法
//        int pivot = partitionHole(array, start, end);//挖坑法
        int pivot = partition(array, start, end);//双指针法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //三数取中
    private int middleNum(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        if(array[left] < array[right])
        {
            if(array[mid] < array[left])
            {
                return left;
            }
            else if(array[mid] > array[right])
            {
                return right;
            }
            else {
                return mid;
            }
        }
        else
        {
            if(array[mid] < array[right])
            {
                return right;
            }
            else if(array[mid] > array[left])
            {
                return left;
            }
            else
            {
                return mid;
            }
        }
    }

    private int partition(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right)
        {
            if(array[cur] < array[left] && array[++prev] != array[cur])
            {
                swap(array, prev, cur);
            }
            cur++;
        }
        swap(array, left, prev);
        return prev;
    }

    //2.挖坑法
    private int partitionHole(int[] array, int left, int right) {
        int tmp = array[left];
        while(left < right)
        {
            while (left < right && array[right] >= tmp)
            {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp)
            {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    //1.Hoare
    private int partitionHoare(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;
        while (left < right)
        {
            while (left < right && array[right] >= tmp)
            {
                right--;
            }
            while (left < right && array[left] <= tmp)
            {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, i, left);
        return left;
    }

    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    private void insertSort(int[] array,int left,int right) {
        for (int i = left+1; i <= right; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= left ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
}
